//合并区间
//链接：https://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6a?tpId=295&tqId=691&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param intervals Interval类vector 
     * @return Interval类vector
     */
    vector<Interval> merge(vector<Interval>& intervals) {
        //按start升序
        std::sort(intervals.begin(), intervals.end(), [](Interval& l, Interval& r)     {return l.start < r.start;});
        //从左往右开始合并，贪心思想
        vector<Interval> answer;
        int size = intervals.size();
        //空或一个
        if (size < 2) {return intervals;}

        //多个
        int i = 0, j = 1;
        while (j < size)
        {
            int max_end = intervals[i].end;//处理比如：[[1,10],[4,5],[6,9][8,10]]
            int k = i;
            while (j < size)
            {
                if (intervals[j].start <= intervals[j - 1].end)
                {
                    if (max_end < intervals[j].end) {max_end = intervals[j].end;}
                }
                else 
                {
                    if (intervals[j].start <= max_end) {max_end = std::max(intervals[j].end, max_end);}
                    else break;
                }
                ++j;
            }
            answer.push_back(Interval(intervals[i].start, max_end));
            i = j;
            ++j;
            if (i == size - 1)//最后一个区间
            {
                answer.push_back(intervals[i]);
            }
        }
        return answer;
    }
};

//归并排序
void MergeSort(vector<int>& vt)
{
	int size = vt.size();
	vector<int> tmp(vt);
	int left_1 = 0, right_1 = 0, left_2 = 0, right_2 = 0;
	int gap = 1;
	while (gap < size)
	{
		for (int i = 0; i < size;  )
		{
			left_1 = i;
			right_1 = i + gap -1;
			if (right_1 >= size - 1) { break; }

			left_2 = right_1 + 1;
			right_2 = left_2 + gap - 1;
			if (right_2 >= size - 1) { right_2 = size - 1; }

			int index = left_1;
			while (left_1 <= right_1 && left_2 <= right_2)
			{
				if (vt[left_1] <= vt[left_2])	
				{
					tmp[index] = vt[left_1++];
				}
				else { tmp[index] = vt[left_2++]; }
				++index;
			}
			while (left_1 <= right_1) { tmp[index++] = vt[left_1++]; }
			while (left_2 <= right_2) { tmp[index++] = vt[left_2++]; }

			i = index;
		}
		vt = tmp;
		gap *= 2;
	}
}

int main()
{
	vector<int> vt{ 45, 12, 67, 0, 6, 3, 4, 3, 0, 0, -7, -8, 1 , 100, 45, 78, 0, 0, 9, 0};
	MergeSort(vt);
	for (auto& e : vt)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}